1. Field of the Invention
The present invention relates to a curve approximation method for approximating a curved portion of a contour of a character or picture, etc., by using a curve approximation function. The present invention is utilized for approximating the contour of the character, etc., by straight lines and curves to compress and store the pattern data of the character, and is particularly used in industry for computers, word-processors, and computerized type-setting.
2. Description of the Related Art
A method in which the total number of dots constituting the pattern of the character are stored is known. However, in this method, too much data must be stored, and when an enlarged pattern and reduced pattern, etc., of the original pattern are produced on the basis of the total number of dots of the pattern, an obligue line and curved stroke (referred to as curved stroke hereinafter) can not be made smooth, and therefore, a high quality pattern can not be obtained.
Accordingly, a pattern compressing method in which only a small amount of pattern data of the character and picture, etc., need be stored, and a high quality pattern can be obtained when enlargement and reduction are carried out, has become necessary. A method is known in which the pattern is represented by a contour, and this method is effective for data compression. That is, the contour of the pattern is approximated by straight lines and curves, and only the data relating to the approximated straight lines and curves is stored, thereby reducing the amount of the data to be stored. A high quality pattern for expansion or reduction, etc., can be obtained by this method.
A method in which the contour of the character pattern is expressed by an approximated curve is disclosed in UK Patent Application GB No. 2147474A to the Shaken Co., Ltd., entitled "Method of processing character or pictorial image data" and published on May 9, 1985, and will be explained hereinafter.
That is, in this method, the curve approximation is carried out by sequentially changing the segment, using a residual as an evaluation standard, and the segment is approximated by using a spline function on the basis of slopes and coordinates at both end points. The function representing the curve must be a single-value function with respect to one axis, for example, an X-axis, when the contour is approximated by curves. Therefore, these segments traced on the contour of the character are divided into sections wherein only one y-value exists with respect to one X-value.
The curved portion is expressed by a polynominal of the n-th degree (n=2 or 3). The coefficient of the polynominal of the n-th degree is determined on the basis of slopes and coordinates at both end points of an interval to be curve-approximated. To carry out the curve approximation, the slope at each contour point (the point on the contour) is calculated, the approximate curve is determined on the basis of two contour points on the contour, the deviation between the approximate curve and the contour is calculated with respect to each contour point, the contour point is moved forward by one to repeat the same process when the deviation with respect to the curve approximate interval now in question is less than an allowable error, the longest interval (sampling interval) wherein the deviation is within the allowable error is determined, and the contour is divided into these sampling intervals.
However, this prior art method has a low processing speed, since the calculation of the approximate curve is repeated until the deviation exceeds the allowable error.
Further, this method does not always realize a correct curve approximation, since the method does not consider the curve vibration phenomenon. That is, the possibility of the occurrence of vibration of the approximated curve obtained by afore-mentioned method. This vibration can be detected by determining whether or not the approximated curve as a maximal value and/or a minimal value (referred as an extreme value hereinafter). But, if the contour is divided according to the method of the prior art, to carry out the curve approximation, a curve having an extreme value may exist. Accordingly, it is not easy to detect the vibration by finding the extreme value within the approximation interval.